package q496_nextGreaterElement;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Solution {
    /*
    标准的单调栈
    只不过使用了两个数组来增加操作数量
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        // 对于nums1 使用一个map来存储每一个元素以及它原有的索引位置
        // 这样做能够有效的复用nums1作为返回的答案
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        // 单调栈来寻找对于每一个数其右侧 第一个 大于 它的数
        Deque<Integer> stack = new LinkedList<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                stack.pop();
            }
            // 判断contains
            if (map.containsKey(nums2[i])) {
                nums1[map.get(nums2[i])] = stack.isEmpty() ? -1 : nums2[stack.peek()];
            }
            stack.push(i);
        }

        return nums1;
    }
}
